package swordoffer.offer33;

public class RecursionSolution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    public boolean recur(int[] arr, int lo, int hi) {
        // base case
        if (lo >= hi) {
            return true;
        }
        int mid = lo;
        // 找到右子树跟节点的索引
        for (int i = lo; i <= hi; i++) {
            if (arr[i] < arr[hi]) {
                mid++;
            }
        }
        // 判断右子树是否符合二叉搜索树的条件
        for (int i = mid; i < hi; i++) {
            if (arr[i] < arr[hi]) {
                return false;
            }
        }
        // 递归判断左子树和右子树是否是二叉搜索树
        return recur(arr, lo, mid - 1) && recur(arr, mid, hi - 1);
    }
}
